#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int val = 0;
        for (auto e : nums)
        {
            val ^= e;
        }

        return val;
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        int ret = nums[0];
        int count = 1;
        int n = nums.size();
        for (int i = 1; i < n; i++)
        {
            if (ret != nums[i])
            {
                count--;
                if (count == 0)
                {
                    count = 1;
                    ret = nums[i];
                }
            }
            else count++;

        }

        return ret;
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int n = nums.size();
        int left = -1, right = n;
        int i = 0;
        while (i < right)
        {
            if (nums[i] < 1)
            {
                swap(nums[++left], nums[i++]);
            }
            else if (nums[i] == 1)
            {
                i++;
            }
            else
            {
                swap(nums[--right], nums[i]);
            }
        }
    }
};

class Solution {
public:
    void nextPermutation(vector<int>& nums)
    {
        int pos1 = nums.size() - 2;
        while (pos1 >= 0 && nums[pos1] >= nums[pos1 + 1])
        {
            pos1--;
        }
        if (pos1 < 0) sort(nums.begin(), nums.end());
        else
        {
            int pos2 = nums.size() - 1;
            while (nums[pos2] <= nums[pos1]) pos2--;
            swap(nums[pos2], nums[pos1]);
            reverse(nums.begin() + pos1 + 1, nums.end());
        }
    }
};

class Solution {
public:
    int findDuplicate(vector<int>& nums)
    {
        int slow = 0, fast = 0;
        while (true)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }

        slow = 0;
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};